Plus loin que la mémoisation : la tabulation

by serge-sans-paille

QuarksLab

PyConFR 2015, Pau

Qui suis-je ?

In [2]:
class Namek: pass
class Quarkslab: pass
In [3]:
class SergeSansPaille(Quarkslab, Namek):
    '''
    /me likes docstrings
    '''

    def work(self, *args, **kwargs):
        raise RuntimeError("not a good idea")

    def run(self):
        while 1:
            pass  # that's very fast!

    def hack(self, project):
        return project.name in ('pythran', 'llvm') or project.lang in ('python', 'c++')

Trou de mémoire

In [4]:
from functools import lru_cache

def fibo(n): # how no, not *you* again!
    return n if n < 2 else (fibo(n-1) + fibo(n-2))

@lru_cache(maxsize=20)
def memfibo(n): # how no, not *you* again!
    return n if n < 2 else (memfibo(n-1) + memfibo(n-2))
In [5]:
%timeit fibo(20)

100 loops, best of 3: 2.16 ms per loop
In [6]:
%timeit memfibo(20), memfibo.cache_clear()

10000 loops, best of 3: 68.9 µs per loop

Et si on poussait l'idée à l'extrême?

In [7]:
def P(v):
    c = 0
    while v:
        c += v&1
        v>>=1
    return c

Pm = lru_cache(maxsize=1<<16)(P)
In [8]:
l = list(range(1<<16))
In [9]:
%timeit [P(x) for x in l]

10 loops, best of 3: 102 ms per loop
In [10]:
%timeit [Pm(x) for x in l]

1 loops, best of 3: 92.7 ms per loop

Non, vraiment à l'extrême !

In [11]:
def tabulate(P):
    
    import numpy as np
    
    class Tabulated(object):
        
        def __init__(self):
            self.tabulated = np.array([P(x) for x in range(1<<16)],
                                      dtype=np.uint8)
    
        def __call__(self, x):
            return int(self.tabulated[x])
        
    return Tabulated()
    
Pt = tabulate(P)
In [12]:
%timeit [P(x) for x in l]

10 loops, best of 3: 100 ms per loop
In [13]:
%timeit [Pt(x) for x in l]

10 loops, best of 3: 21 ms per loop

Plus fort que la mémoisation : la tabulation

  1. Précalculer tous les appels de la fonction, suivant le domaine d'entrée
  2. Utiliser une Look Up Table pour remplacer l'appel de fonction

Problèmes

  1. Définition du domaine d'entrée
  2. Type de sortie
  3. Taille de la LUT
  4. Temps d'exécution

Annotations

On peut utiliser les annotations d'argument ppour calculer l'ensemble des valeurs possibles

In [14]:
from numpy import uint16, uint8

def P(v:uint16) -> uint8:
    c = 0
    while v:
        c += v&1
        v>>=1
    return c

Compression

En un morceau

Compression de la LUT, en un bloc

In [15]:
def tabulate(P):
    import numpy, lz4
    
    class Tabulated(object):
        def __init__(self):
            self.tabulated = lz4.compress(
                numpy.array([P(x) for x in range(1<<16)],
                            dtype=numpy.uint8))
    
        def __call__(self, x):
            return int(lz4.decompress(self.tabulated)[x])
        
    return Tabulated()
In [16]:
Ptc = tabulate(P)
In [17]:
len(Pt.tabulated), len(Ptc.tabulated)
Out[17]:
(65536, 616)
In [18]:
%timeit [P(x) for x in l]
%timeit [Pt(x) for x in l]
%timeit [Ptc(x) for x in l]

10 loops, best of 3: 100 ms per loop
10 loops, best of 3: 21 ms per loop
1 loops, best of 3: 387 ms per loop

→ Pas glop

Compression

par morceaux

tabulated = compress([xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx])

→

tabulateds = [ compress([xxxxxxxxxxxxxxxxxxxxxx]), ..., compress([xxxxxxxxxxxxxxxxxxxxxxxxx])]

En utilisant un algo qui décompresse vite, ça devrait passer!

In [19]:
def tabulate(P):
    import numpy, lz4

    size = 1 << 16
    chunk_size = 1 << 10
        
    class Tabulated(object):

        def __init__(self):
            self.tabulateds = [lz4.compress(numpy.array([P(x) for x in range(i*chunk_size, (i+1) * chunk_size)],
                                                        dtype=numpy.uint8))
                               for i in range(0, size, chunk_size)]

        def __call__(self, x):
            chunk_id = x // chunk_size
            return int(lz4.decompress(self.tabulateds[chunk_id])[x - chunk_id * chunk_size])
        
    return Tabulated()
In [20]:
Ptcm = tabulate(P)
In [21]:
len(Ptc.tabulated), sum(map(len,Ptcm.tabulateds)), len(Pt.tabulated)
Out[21]:
(616, 8704, 65536)
In [22]:
%timeit [P(x) for x in l]
%timeit [Ptc(x) for x in l]
%timeit [Ptcm(x) for x in l]

10 loops, best of 3: 105 ms per loop
1 loops, best of 3: 385 ms per loop
10 loops, best of 3: 55.9 ms per loop

\o/

Et la sécurité dans tout ça ?

  • L'obfuscation, un moyen très utilisé pour « protéger » ses données ou ses algos (même en Python !)
  • Objectif : rendre une attaque en boîte blanche équivalente à une attaque en boîte noire

Attaque en boîte blanche

In [23]:
import inspect
print(inspect.getsource(P))

def P(v:uint16) -> uint8:
    c = 0
    while v:
        c += v&1
        v>>=1
    return c
In [24]:
import dis
dis.dis(P)

  4           0 LOAD_CONST               1 (0)
              3 STORE_FAST               1 (c)

  5           6 SETUP_LOOP              34 (to 43)
        >>    9 LOAD_FAST                0 (v)
             12 POP_JUMP_IF_FALSE       42

  6          15 LOAD_FAST                1 (c)
             18 LOAD_FAST                0 (v)
             21 LOAD_CONST               2 (1)
             24 BINARY_AND
             25 INPLACE_ADD
             26 STORE_FAST               1 (c)

  7          29 LOAD_FAST                0 (v)
             32 LOAD_CONST               2 (1)
             35 INPLACE_RSHIFT
             36 STORE_FAST               0 (v)
             39 JUMP_ABSOLUTE            9
        >>   42 POP_BLOCK

  8     >>   43 LOAD_FAST                1 (c)
             46 RETURN_VALUE

Attaque en boîte noire

In [25]:
P(0), P(1), P(2), P(3), P(4), P(5), P(6) #...
Out[25]:
(0, 1, 1, 2, 1, 2, 2)

Ou alors...

In [26]:
Pt.tabulated[:7]
Out[26]:
array([0, 1, 1, 2, 1, 2, 2], dtype=uint8)

Tabulation $\simeq$ Boîte noire

  • L'attaquant a uniquement accès à la table des fonctions
  • Plus d'information sur la méchanique interne
  • On est sympa, on a fait l'explorationdes valeurs à sa place

→ Impossible de passer par un décorateur, ça suppose la connaissance du code de la fonction décorée

In [27]:
!cat P.py

from numpy import uint16, uint8
def P(v:uint16) -> uint8:
    c = 0
    while v:
        c += v&1
        v>>=1
    return c
In [28]:
!python3 tabulate.py P --compress < P.py > Ptc.py
In [29]:
import Ptc
print(inspect.getsource(type(Ptc.P)))

class P :
	import numpy
	import lz4
	def __init__(self):
		self.cache = {}
		self.tabulated_results = [		 b'\x00\x04\x00\x00\x80\x00\x01\x01\x02\x01\x02\x02\x03\x04\x00D\x02\x03\x03\x04\x08\x00\x00\x0c\x00L\x03\x04\x04\x05\x10\x00\x04\x18\x00\x00\x1c\x00O\x04\x05\x05\x06 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x05\x06\x06\x07@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x06\x07\x07\x08\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x07\x08\x08\t\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x07\x08\x08\t\x08\t\t\n' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x01\x02\x02\x03\x02\x03\x03\x04\x04\x00D\x03\x04\x04\x05\x08\x00\x00\x0c\x00L\x04\x05\x05\x06\x10\x00\x04\x18\x00\x00\x1c\x00O\x05\x06\x06\x07 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x06\x07\x07\x08@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x07\x08\x08\t\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x08\t\t\n\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x08\t\t\n\t\n\n\x0b' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x02\x03\x03\x04\x03\x04\x04\x05\x04\x00D\x04\x05\x05\x06\x08\x00\x00\x0c\x00L\x05\x06\x06\x07\x10\x00\x04\x18\x00\x00\x1c\x00O\x06\x07\x07\x08 \x00\r\x0c0\x00\x048\x00\x00<\x00O\x07\x08\x08\t@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x08\t\t\n\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\t\n\n\x0b\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\t\n\n\x0b\n\x0b\x0b\x0c' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x03\x04\x04\x05\x04\x05\x05\x06\x04\x00D\x05\x06\x06\x07\x08\x00\x00\x0c\x00L\x06\x07\x07\x08\x10\x00\x04\x18\x00\x00\x1c\x00O\x07\x08\x08\t \x00\r\x0c0\x00\x048\x00\x00<\x00O\x08\t\t\n@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\t\n\n\x0b\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\n\x0b\x0b\x0c\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\n\x0b\x0b\x0c\x0b\x0c\x0c\r' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x04\x05\x05\x06\x05\x06\x06\x07\x04\x00D\x06\x07\x07\x08\x08\x00\x00\x0c\x00L\x07\x08\x08\t\x10\x00\x04\x18\x00\x00\x1c\x00O\x08\t\t\n \x00\r\x0c0\x00\x048\x00\x00<\x00O\t\n\n\x0b@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\n\x0b\x0b\x0c\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0b\x0c\x0c\r\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0b\x0c\x0c\r\x0c\r\r\x0e' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x05\x06\x06\x07\x06\x07\x07\x08\x04\x00D\x07\x08\x08\t\x08\x00\x00\x0c\x00L\x08\t\t\n\x10\x00\x04\x18\x00\x00\x1c\x00O\t\n\n\x0b \x00\r\x0c0\x00\x048\x00\x00<\x00O\n\x0b\x0b\x0c@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0b\x0c\x0c\r\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\x0c\r\r\x0e\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\x0c\r\r\x0e\r\x0e\x0e\x0f' ,
		 b'\x00\x04\x00\x00\x80\x06\x07\x07\x08\x07\x08\x08\t\x04\x00D\x08\t\t\n\x08\x00\x00\x0c\x00L\t\n\n\x0b\x10\x00\x04\x18\x00\x00\x1c\x00O\n\x0b\x0b\x0c \x00\r\x0c0\x00\x048\x00\x00<\x00O\x0b\x0c\x0c\r@\x00-\x0f`\x00\r\x0cp\x00\x04x\x00\x00|\x00O\x0c\r\r\x0e\x80\x00m\x0f\xc0\x00-\x0f\xe0\x00\r\x0c\xf0\x00\x04\xf8\x00\x00\xfc\x00O\r\x0e\x0e\x0f\x00\x01\xed\x0f\x80\x01m\x0f\xc0\x01-\x0f\xe0\x01\r\x0c\xf0\x01\x04\xf8\x01\x80\r\x0e\x0e\x0f\x0e\x0f\x0f\x10' ,
]

	def __call__(self, *args): return P.numpy.frombuffer(P.lz4.decompress(self.tabulated_results[args[-1] // 1024]), dtype=P.numpy.uint8).reshape(-1).item(*args[:-1]+(args[-1] % 1024,))
In [30]:
%timeit [P(x) for x in l]

10 loops, best of 3: 106 ms per loop
In [31]:
%timeit [Ptc.P(x) for x in l]

1 loops, best of 3: 329 ms per loop

Avec un petit mécanisme de cache...

In [32]:
!python3 tabulate.py P --compress --cache-depth=2 < P.py > Ptcc.py
In [33]:
import Ptcc
l = list(range((1 << 16)))
%timeit [Ptcc.P(x) for x in l]

1 loops, best of 3: 277 ms per loop

Exemple concluant

Une des briques de l'algo MD5

In [34]:
!cat F.py

from numpy import uint8
def F(x:uint8, y:uint8, z:uint8):
        return (x & y) | ((~x) & z)
In [35]:
!python3 tabulate.py --compress --cache-depth=2 < F.py > Ftcc.py
In [36]:
import F, Ftcc
import itertools
l = range((1 << 4) )

%timeit [F.F(*args) for args in itertools.product(l,l,l)]

1000 loops, best of 3: 1.19 ms per loop
In [37]:
%timeit [Ftcc.F(*args) for args in itertools.product(l,l,l)]

100 loops, best of 3: 13.7 ms per loop

Kenavo

  • La boîte noire parfaite n'est pas un mythe
  • Les idées les plus stupides peuvent fonctionner
  • Avec un peu de siouxeries

Aller plus loin

  • Brancher ça sur Pythran pour générer les tabulations plus rapidement
  • S'inspirer de Blosc/Bcolz pour stocker les tables sur disques